<!DOCTYPE html>
<html lang="en">
    <head>
        <meta charset="UTF-8" />
        <meta http-equiv="X-UA-Compatible" content="IE=edge" />
        <meta name="viewport" content="width=device-width, initial-scale=1.0" />
        <title>Document</title>
    </head>
    <body>
        <script>
            /*
                        思路：N皇后要求的是行、列不能并行、对角线不能相连

                        终止条件：搜索到了叶子节点的位置，就说明找到了所有皇后的点位。就可以return
                        因为是二维数组，每次遍历需要找到对应层的集合，因此需要一个row来记录
                        if(row==n){ return }

                        单层搜索逻辑：chessboard[row]就是对应的单层集合，因此遍历单层集合即可,每一层长度都是n，当然也可以用chessboard[row].length
                        for(let i=0;i<n;i++){
                            if(isValid(row,i,chessboard,n))  //验证它是否行、列、对角线不相交
                            {
                                chessboard[row][i]='Q'
                                backTracking()
                                chessboard[row][i]='.'
                            }
                        }

                        因此难点在于isValid函数的实现
                        */
            var solveNQueens = function (n) {
                //初始化棋盘
                const chessboard = new Array(n).fill([]).map(() => new Array(n).fill('.'))
                const result = []
                //将每一层拼接为字符串
                function transform(chessboard) {
                    let chessboardStrArr = []
                    chessboard.forEach((item) => {
                        chessboardStrArr.push(item.join(''))
                    })
                    return chessboardStrArr
                }
                function backTracking(row, chessboard) {
                    if (row == n) {
                        result.push(transform(chessboard))
                        return
                    }
                    //遍历每一层的集合
                    for (let j = 0; j < n; j++) {
                        if (isValid(row, j, chessboard, n)) {
                            chessboard[row][j] = 'Q'
                            backTracking(row + 1, chessboard)
                            chessboard[row][j] = '.'
                        }
                    }
                }

                //先实现isValid函数
                function isValid(row, col, chessboard, n) {
                    //为什么不需要检查同行呢，因为递归的时候，每一行也只会选一个变为Q，然后就进入了下一层了
                    //检查是否同列
                    for (let i = 0; i < row; i++) {
                        if (chessboard[i][col] == 'Q') {
                            return false
                        }
                    }
                    //检查135°角
                    for (let i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
                        if (chessboard[i][j] == 'Q') {
                            return false
                        }
                    }
                    //检查45°角，即斜着向上
                    for (let i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
                        if (chessboard[i][j] == 'Q') {
                            return false
                        }
                    }
                    return true
                }
                backTracking(0, chessboard)
                return result
            }
            solveNQueens(3)
        </script>
    </body>
</html>
